package 动态规划.可dp可二分;

import org.junit.Test;

import javax.swing.*;
import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/9/15 21:51
 */
public class lc410新思考 {






    public int recursion(int index,int m,int nums[],Integer dp[][],int preSum[]){
        // basecase
        if(index == nums.length && m == 0){
            return 0;
        }
        if(index == nums.length || m  == 0){ //  不合理的分组，
            return preSum[nums.length];
        }

        int max = 0 , min = Integer.MAX_VALUE;

        for(int i = index + 1;i <= nums.length;i++){ // 这里还可以进行一个小小的剪枝， 比如 不够 m 组可以直接返回
            max = Math.max(recursion(i,m - 1,nums,dp,preSum),preSum[i] - preSum[index]);
            min = Math.min(min,max);
        }

        return min;
    }

    public int solve(int nums[],int m){
        int r = Arrays.stream(nums).sum();
        int l = Arrays.stream(nums).max().getAsInt();

        while(l < r){
            int mid = l + r  >> 1;
            if(check(nums,mid) > m){
                l = mid + 1;
            }else{
                r = mid;
            }
        }
        return l;
    }

    private int check(int[] nums, int mid) {
        int count = 0,sum = 0;
        for (int i = 0; i < nums.length; i++) {
            if(sum + nums[i] > mid){ // 预判断
                count++;
                sum = nums[i];
            }else{
                sum += nums[i];
            }
        }
        return count + 1;
    }


    @Test
    public void test(){
        int nums[] = {7,2,5,10,8};
//        int check = check(nums, 21);
//        System.out.println(check);
        int m = 2;
        int solve = solve(nums, m);
        System.out.println(solve);

    }

}
